Skip to content

Latest commit

 

History

History

03.02.Min Stack

README.md

commentsdifficultyedit_url
true
简单

面试题 03.02. 栈的最小值

English Version

题目描述

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。


示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

解法

方法一：双栈

我们用两个栈来实现，其中stk1 用来存储数据，stk2 用来存储当前栈中的最小值。初始时，stk2 中存储一个极大值。

  • 当我们向栈中压入一个元素 x 时，我们将 x 压入 stk1，并将 min(x, stk2[-1]) 压入 stk2。
  • 当我们从栈中弹出一个元素时，我们将 stk1 和 stk2 的栈顶元素都弹出。
  • 当我们要获取当前栈中的栈顶元素时，我们只需要返回 stk1 的栈顶元素即可。
  • 当我们要获取当前栈中的最小值时，我们只需要返回 stk2 的栈顶元素即可。

时间复杂度：对于每个操作，时间复杂度均为 $O(1)$，空间复杂度 $O(n)$。

Python3

classMinStack: def__init__(self): """ initialize your data structure here. """self.s= [] self.mins= [inf] defpush(self, val: int) ->None: self.s.append(val) self.mins.append(min(self.mins[-1], val)) defpop(self) ->None: self.s.pop() self.mins.pop() deftop(self) ->int: returnself.s[-1] defgetMin(self) ->int: returnself.mins[-1] # Your MinStack object will be instantiated and called as such:# obj = MinStack()# obj.push(val)# obj.pop()# param_3 = obj.top()# param_4 = obj.getMin()

Java

classMinStack { privateDeque<Integer> stk1 = newArrayDeque<>(); privateDeque<Integer> stk2 = newArrayDeque<>(); /** initialize your data structure here. */publicMinStack() { stk2.push(Integer.MAX_VALUE); } publicvoidpush(intx) { stk1.push(x); stk2.push(Math.min(x, stk2.peek())); } publicvoidpop() { stk1.pop(); stk2.pop(); } publicinttop() { returnstk1.peek(); } publicintgetMin() { returnstk2.peek(); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */

C++

classMinStack { public:/** initialize your data structure here. */MinStack() { stk2.push(INT_MAX); } voidpush(int x) { stk1.push(x); stk2.push(min(x, stk2.top())); } voidpop() { stk1.pop(); stk2.pop(); } inttop() { return stk1.top(); } intgetMin() { return stk2.top(); } private: stack<int> stk1; stack<int> stk2; }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin();*/

Go

typeMinStackstruct { stk1 []intstk2 []int } /** initialize your data structure here. */funcConstructor() MinStack { returnMinStack{[]int{}, []int{math.MaxInt32}} } func (this*MinStack) Push(xint) { this.stk1=append(this.stk1, x) this.stk2=append(this.stk2, min(x, this.stk2[len(this.stk2)-1])) } func (this*MinStack) Pop() { this.stk1=this.stk1[:len(this.stk1)-1] this.stk2=this.stk2[:len(this.stk2)-1] } func (this*MinStack) Top() int { returnthis.stk1[len(this.stk1)-1] } func (this*MinStack) GetMin() int { returnthis.stk2[len(this.stk2)-1] } /** * Your MinStack object will be instantiated and called as such: * obj := Constructor(); * obj.Push(x); * obj.Pop(); * param_3 := obj.Top(); * param_4 := obj.GetMin(); */

TypeScript

classMinStack{stack: number[];mins: number[];constructor(){this.stack=[];this.mins=[];}push(x: number): void{this.stack.push(x);this.mins.push(Math.min(this.getMin(),x));}pop(): void{this.stack.pop();this.mins.pop();}top(): number{returnthis.stack[this.stack.length-1];}getMin(): number{returnthis.mins.length==0 ? Infinity : this.mins[this.mins.length-1];}}/** * Your MinStack object will be instantiated and called as such: * var obj = new MinStack() * obj.push(x) * obj.pop() * var param_3 = obj.top() * var param_4 = obj.getMin() */

Rust

use std::collections::VecDeque;structMinStack{stack:VecDeque<i32>,min_stack:VecDeque<i32>,}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */implMinStack{/** initialize your data structure here. */fnnew() -> Self{Self{stack:VecDeque::new(),min_stack:VecDeque::new(),}}fnpush(&mutself,x:i32){self.stack.push_back(x);ifself.min_stack.is_empty() || *self.min_stack.back().unwrap() >= x {self.min_stack.push_back(x);}}fnpop(&mutself){let val = self.stack.pop_back().unwrap();if*self.min_stack.back().unwrap() == val {self.min_stack.pop_back();}}fntop(&self) -> i32{*self.stack.back().unwrap()}fnget_min(&self) -> i32{*self.min_stack.back().unwrap()}}

C#

publicclassMinStack{privateStack<int>stk1=newStack<int>();privateStack<int>stk2=newStack<int>();/** initialize your data structure here. */publicMinStack(){stk2.Push(int.MaxValue);}publicvoidPush(intx){stk1.Push(x);stk2.Push(Math.Min(x,GetMin()));}publicvoidPop(){stk1.Pop();stk2.Pop();}publicintTop(){returnstk1.Peek();}publicintGetMin(){returnstk2.Peek();}}/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.Push(x); * obj.Pop(); * int param_3 = obj.Top(); * int param_4 = obj.GetMin(); */

Swift

classMinStack{privatevarstk1:[Int]privatevarstk2:[Int]init(){ stk1 =[] stk2 =[Int.max]}func push(_ x:Int){ stk1.append(x) stk2.append(min(x, stk2.last!))}func pop(){ stk1.removeLast() stk2.removeLast()}func top()->Int{return stk1.last! }func getMin()->Int{return stk2.last! }} /** * Your MinStack object will be instantiated and called as such: * let obj = MinStack(); * obj.push(x); * obj.pop(); * let param_3 = obj.top(); * let param_4 = obj.getMin(); */
close